use std::collections::HashMap;
use std::fmt::Debug;

#[derive(Debug, Clone)]
pub struct Graph<N, E> 
where 
    N: Debug + Clone,
    E: Debug + Clone,
{
    pub nodes: HashMap<String, N>,
    pub edges: HashMap<(String, String), E>,
    pub directed: bool,
    pub adjacency_list: HashMap<String, Vec<String>>,
}

impl<N, E> Graph<N, E>
where 
    N: Debug + Clone,
    E: Debug + Clone,
{
    // 创建一个新的空图
    pub fn new(directed: bool) -> Self {
        Graph {
            nodes: HashMap::new(),
            edges: HashMap::new(),
            directed,
            adjacency_list: HashMap::new(),
        }
    }

    // 向图中添加节点
    pub fn add_node(&mut self, id: String, node_data: N) {
        self.nodes.insert(id.clone(), node_data);
        self.adjacency_list.entry(id).or_insert_with(Vec::new);
    }

    // 向图中添加边
    pub fn add_edge(&mut self, u: String, v: String, edge_data: E) {
        // 添加边到边集合中
        self.edges.insert((u.clone(), v.clone()), edge_data);
        
        // 更新邻接表
        self.adjacency_list.entry(u.clone()).or_insert_with(Vec::new).push(v.clone());
        if !self.directed {
            // 对于无向图，反向边也要添加
            self.adjacency_list.entry(v.clone()).or_insert_with(Vec::new).push(u);
        }
    }

    // 打印图的信息
    pub fn print_graph(&self) {
        println!("Nodes:");
        for (id, node) in &self.nodes {
            println!("{}: {:?}", id, node);
        }

        println!("\nEdges:");
        for ((u, v), edge) in &self.edges {
            println!("({}, {}): {:?}", u, v, edge);
        }

        println!("\nAdjacency List:");
        for (node, neighbors) in &self.adjacency_list {
            println!("{} -> {:?}", node, neighbors);
        }
    }

     // 删除一个节点
     pub fn remove_node(&mut self, id: &str) {
        // 删除节点在nodes中的记录
        self.nodes.remove(id);

        // 删除该节点的所有边
        self.edges.retain(|(u, v), _| u != id && v != id);

        // 删除邻接表中该节点的记录
        self.adjacency_list.remove(id);

        // 删除邻接表中所有指向该节点的边（对于有向图）
        for neighbors in self.adjacency_list.values_mut() {
            neighbors.retain(|neighbor| neighbor != id);
        }
    }

    // 删除一条边
    pub fn remove_edge(&mut self, u: &str, v: &str) {
        // 删除边的记录
        self.edges.remove(&(u.to_string(), v.to_string()));

        // 更新邻接表，移除相关边
        if let Some(neighbors) = self.adjacency_list.get_mut(u) {
            neighbors.retain(|neighbor| neighbor != v);
        }

        if !self.directed {
            // 对于无向图，反向边也要删除
            if let Some(neighbors) = self.adjacency_list.get_mut(v) {
                neighbors.retain(|neighbor| neighbor != u);
            }
        }
    }

    // pub fn dijkstra(&self, )

}

fn main() {
    // 创建一个无向图
    let mut graph: Graph<String, i32> = Graph::new(false);

    // 添加节点
    graph.add_node("A".to_string(), "Node A".to_string());
    graph.add_node("B".to_string(), "Node B".to_string());
    graph.add_node("C".to_string(), "Node C".to_string());

    // 添加边
    graph.add_edge("A".to_string(), "B".to_string(), 10);
    graph.add_edge("A".to_string(), "C".to_string(), 20);
    graph.add_edge("B".to_string(), "C".to_string(), 30);

    // 打印图的结构
    graph.print_graph();
}
